1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 import static java.util.Collections.*;
32 import java.util.*;
33 import java.util.concurrent.*;
34
35 public class RacingCollections {
36
37
38
39
40
41 final static long defaultWorkTimeMillis = Long.getLong("millis", 10L);
42
43
44
45
46 final static boolean debug = Boolean.getBoolean("debug");
47
48 final static Integer one = 1;
49 final static Integer two = 2;
50
51
52
53
54
55 static class Frobber extends CheckedThread {
56 volatile boolean done = false;
57 boolean keepGoing(int i) { return (i % 128 != 0) || ! done; }
58
59 final Object elLoco;
60 Frobber(Object elLoco) {
61 this.elLoco = elLoco;
62 this.start();
63 }
64
65 @SuppressWarnings("unchecked") void clear(Object o) {
66 if (o instanceof Collection)
67 ((Collection<?>)o).clear();
68 else
69 ((Map<?,?>)o).clear();
70 }
71
72 @SuppressWarnings("unchecked") void realRun() {
73
74 clear(elLoco);
75 if (elLoco instanceof List) {
76 List<Integer> l = (List<Integer>) elLoco;
77 for (int i = 0; keepGoing(i); i++) {
78 switch (i%2) {
79 case 0: l.add(two); break;
80 case 1: l.add(0, two); break;
81 }
82 switch (i%2) {
83 case 0: l.remove(two); break;
84 case 1: l.remove(0); break;
85 }}}
86 else if (elLoco instanceof Deque) {
87 Deque<Integer> q = (Deque<Integer>) elLoco;
88 for (int i = 0; keepGoing(i); i++) {
89 switch (i%6) {
90 case 0: q.add(two); break;
91 case 1: q.addFirst(two); break;
92 case 2: q.addLast(two); break;
93 case 3: q.offer(two); break;
94 case 4: q.offerFirst(two); break;
95 case 5: q.offerLast(two); break;
96 }
97 switch (i%6) {
98 case 0: q.remove(two); break;
99 case 1: q.removeFirst(); break;
100 case 2: q.removeLast(); break;
101 case 3: q.poll(); break;
102 case 4: q.pollFirst(); break;
103 case 5: q.pollLast(); break;
104 }}}
105 else if (elLoco instanceof Queue) {
106 Queue<Integer> q = (Queue<Integer>) elLoco;
107 for (int i = 0; keepGoing(i); i++) {
108 switch (i%2) {
109 case 0: q.add(two); break;
110 case 1: q.offer(two); break;
111 }
112 switch (i%2) {
113 case 0: q.remove(two); break;
114 case 1: q.poll(); break;
115 }}}
116 else if (elLoco instanceof Map) {
117 Map<Integer, Boolean> m = (Map<Integer, Boolean>) elLoco;
118 for (int i = 0; keepGoing(i); i++) {
119 m.put(two, true);
120 m.remove(two);
121 }}
122 else if (elLoco instanceof Collection) {
123 Collection<Integer> c = (Collection<Integer>) elLoco;
124 for (int i = 0; keepGoing(i); i++) {
125 c.add(two);
126 c.remove(two);
127 }}
128 else { throw new Error("Huh? " + elLoco); }
129 }
130
131 void enoughAlready() {
132 done = true;
133 try { join(); } catch (Throwable t) { unexpected(t); }
134 }
135 }
136
137 private static void checkEqualSanity(Object theRock, Object elLoco) {
138
139 equal(elLoco, elLoco);
140
141
142
143
144
145
146
147
148 notEqual(theRock.toString(), elLoco.toString());
149 }
150
151 static class Looper {
152 final long quittingTime;
153 int i = 0;
154 Looper() { this(defaultWorkTimeMillis); }
155 Looper(long workTimeMillis) {
156 quittingTime = System.nanoTime() + workTimeMillis * 1024 * 1024;
157 }
158 boolean keepGoing() {
159 return (i++ % 128 != 0) || (System.nanoTime() < quittingTime);
160 }
161 }
162
163 private static void frob(Object theRock, Object elLoco) {
164 Frobber frobber = new Frobber(elLoco);
165 try {
166 if (theRock instanceof Collection) {
167 @SuppressWarnings("unchecked")
168 Collection<Integer> c = (Collection<Integer>) theRock;
169 if (! c.contains(one))
170 c.add(one);
171 } else {
172 @SuppressWarnings("unchecked")
173 Map<Integer, Boolean> m = (Map<Integer, Boolean>) theRock;
174 if (! m.containsKey(one))
175 m.put(one, true);
176 }
177 for (Looper looper = new Looper(); looper.keepGoing(); )
178 checkEqualSanity(theRock, elLoco);
179 }
180 catch (Throwable t) { unexpected(t); }
181 finally { frobber.enoughAlready(); }
182 }
183
184 private static List<Map<Integer, Boolean>> newConcurrentMaps() {
185 List<Map<Integer, Boolean>> list =
186 new ArrayList<Map<Integer, Boolean>>();
187 list.add(new ConcurrentHashMap<Integer, Boolean>());
188 list.add(new ConcurrentSkipListMap<Integer, Boolean>());
189 return list;
190 }
191
192 private static List<Map<Integer, Boolean>> maps() {
193 List<Map<Integer, Boolean>> list = newConcurrentMaps();
194 list.add(new Hashtable<Integer, Boolean>());
195 list.add(new HashMap<Integer, Boolean>());
196 list.add(new TreeMap<Integer, Boolean>());
197 Comparator<Integer> cmp = new Comparator<Integer>() {
198 public int compare(Integer x, Integer y) {
199 return x - y;
200 }};
201 list.add(new TreeMap<Integer, Boolean>(Collections.reverseOrder(cmp)));
202 return list;
203 }
204
205 private static List<Set<Integer>> newConcurrentSets() {
206 List<Set<Integer>> list = new ArrayList<Set<Integer>>();
207 list.add(new ConcurrentSkipListSet<Integer>());
208 list.add(new CopyOnWriteArraySet<Integer>());
209 return list;
210 }
211
212 private static List<Set<Integer>> newSets() {
213 List<Set<Integer>> list = newConcurrentSets();
214 list.add(new HashSet<Integer>());
215 list.add(new TreeSet<Integer>());
216 list.add(new TreeSet<Integer>(Collections.reverseOrder()));
217 return list;
218 }
219
220 private static List<List<Integer>> newConcurrentLists() {
221 List<List<Integer>> list = new ArrayList<List<Integer>>();
222 list.add(new CopyOnWriteArrayList<Integer>());
223 return list;
224 }
225
226 private static List<List<Integer>> newLists() {
227 List<List<Integer>> list = newConcurrentLists();
228 list.add(new Vector<Integer>());
229 list.add(new ArrayList<Integer>());
230 return list;
231 }
232
233 private static List<Queue<Integer>> newConcurrentQueues() {
234 List<Queue<Integer>> list =
235 new ArrayList<Queue<Integer>>(newConcurrentDeques());
236 list.add(new LinkedBlockingQueue<Integer>(10));
237 list.add(new LinkedTransferQueue<Integer>());
238 list.add(new ConcurrentLinkedQueue<Integer>());
239 return list;
240 }
241
242 private static List<Queue<Integer>> newQueues() {
243 List<Queue<Integer>> list =
244 new ArrayList<Queue<Integer>>(newDeques());
245 list.add(new LinkedBlockingQueue<Integer>(10));
246 return list;
247 }
248
249 private static List<Deque<Integer>> newConcurrentDeques() {
250 List<Deque<Integer>> list = new ArrayList<Deque<Integer>>();
251 list.add(new LinkedBlockingDeque<Integer>(10));
252 list.add(new ConcurrentLinkedDeque<Integer>());
253 return list;
254 }
255
256 private static List<Deque<Integer>> newDeques() {
257 List<Deque<Integer>> list = newConcurrentDeques();
258 list.add(new ArrayDeque<Integer>());
259 list.add(new LinkedList<Integer>());
260 return list;
261 }
262
263 private static void describe(Class<?> k, Object x, Object y) {
264 if (debug)
265 System.out.printf("%s: %s, %s%n", k.getSimpleName(),
266 x.getClass().getSimpleName(),
267 y.getClass().getSimpleName());
268 }
269
270 private static void realMain(String[] args) {
271 for (Map<Integer, Boolean> x : maps())
272 for (Map<Integer, Boolean> y : newConcurrentMaps()) {
273 describe(Map.class, x, y);
274 x.put(one, true);
275 frob(x, y);
276 frob(unmodifiableMap(x), y);
277 frob(synchronizedMap(x), y);
278 frob(x, synchronizedMap(y));
279 frob(checkedMap(x, Integer.class, Boolean.class), y);
280 frob(x, checkedMap(y, Integer.class, Boolean.class));
281 x.clear();
282 frob(newSetFromMap(x), newSetFromMap(y));
283 frob(x.keySet(), newSetFromMap(y));
284 }
285
286 for (Set<Integer> x : newSets())
287 for (Set<Integer> y : newConcurrentSets()) {
288 describe(Set.class, x, y);
289 frob(x, y);
290 frob(unmodifiableSet(x), y);
291 frob(synchronizedSet(x), y);
292 frob(x, synchronizedSet(y));
293 frob(checkedSet(x, Integer.class), y);
294 frob(x, checkedSet(y, Integer.class));
295 }
296
297 for (List<Integer> x : newLists())
298 for (List<Integer> y : newConcurrentLists()) {
299 describe(List.class, x, y);
300 frob(x, y);
301 frob(unmodifiableList(x), y);
302 frob(synchronizedList(x), y);
303 frob(x, synchronizedList(y));
304 frob(checkedList(x, Integer.class), y);
305 frob(x, checkedList(y, Integer.class));
306 }
307
308 for (Queue<Integer> x : newQueues())
309 for (Queue<Integer> y : newConcurrentQueues()) {
310 describe(Queue.class, x, y);
311 frob(x, y);
312 }
313
314 for (Deque<Integer> x : newDeques())
315 for (Deque<Integer> y : newConcurrentDeques()) {
316 describe(Deque.class, x, y);
317 frob(asLifoQueue(x), y);
318 frob(x, asLifoQueue(y));
319 }
320 }
321
322
323 static volatile int passed = 0, failed = 0;
324 static void pass() {passed++;}
325 static void fail() {failed++; Thread.dumpStack();}
326 static void fail(String msg) {System.out.println(msg); fail();}
327 static void unexpected(Throwable t) {failed++; t.printStackTrace();}
328 static void check(boolean cond) {if (cond) pass(); else fail();}
329 static String toString(Object x) {
330 return ((x instanceof Collection) || (x instanceof Map)) ?
331 x.getClass().getName() : x.toString();}
332 static void equal(Object x, Object y) {
333 if (x == null ? y == null : x.equals(y)) pass();
334 else fail(toString(x) + " not equal to " + toString(y));}
335 static void notEqual(Object x, Object y) {
336 if (x == null ? y == null : x.equals(y))
337 fail(toString(x) + " equal to " + toString(y));
338 else pass();}
339 public static void main(String[] args) throws Throwable {
340 try {realMain(args);} catch (Throwable t) {unexpected(t);}
341 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
342 if (failed > 0) throw new AssertionError("Some tests failed");}
343 private static abstract class CheckedThread extends Thread {
344 abstract void realRun() throws Throwable;
345 public void run() {
346 try { realRun(); } catch (Throwable t) { unexpected(t); }}}
347 }